package zhoujian.oj.leetcode;

import org.junit.Test;

/**
 * @author hyper
 * @email zjkermit@gmail.com
 * @date 2014-2-17
 * @version 1.0
 * @description Given two numbers represented as strings, return multiplication
 *              of the numbers as a string.
 * 
 *              Note: The numbers can be arbitrarily large and are non-negative.
 */
public class MultiplyStrings {

	@Test
	public void test() {
		String num1 = "98";
		String num2 = "9";
		System.out.println(multiply(num1, num2));
	}
	
	public String multiply(String num1, String num2) {
		if (num1.length() == 0 || num2.length() == 0) return "0";
		// the length of result would not beyond the sum of two length
		int len = num1.length() + num2.length();
		int[] res = new int[len];	// store result
		StringBuilder sb = new StringBuilder();	// store result
		int carry = 0;
		for (int i = 0; i < num1.length(); i++) {
			char c1 = num1.charAt(num1.length() - i - 1);
			int n1 = c1 - '0';
			carry = 0;
			for (int j = 0; j < num2.length(); j++) {
				char c2 = num2.charAt(num2.length() - j - 1);
				int n2 = c2 - '0';
				int temp = n1 * n2 + res[i + j] + carry;
				res[i + j] = temp % 10;
				carry = temp / 10;
			}
			res[i + num2.length()] = carry;
		}
		boolean flag = true;
		for (int i = res.length - 1; i >= 0; i--) {
			if (flag && res[i] == 0) {
				continue;
			} else {
				flag = false;
			}
			sb.append(res[i]);
		}
		if (sb.length() == 0) sb.append(0); 
		return sb.toString();
	}

}
